class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        n = len(nums)
        if n==0:
            return 0
        a = [0] * (n+2)
        a[0] = a[n+1] = 1
        for i in range(1,n+1):
            a[i] = nums[i-1]
        f = [[0] * (n+2) for _ in range(n+2)]
        for lens in range(3,n+3):
            for i in range(n-lens+2+1):
                j= i+lens-1
                for k in range(i+1,j):
                    f[i][j] = max(f[i][j],f[i][k] + f[k][j] + a[i] *a[k] *a[j])
        return f[0][n+1]


a= [3,1,5,8]
s=Solution()
m=s.maxCoins(a)
print(m)